/**
 * In England the currency is made up of pound, P, and pence, p, and there 
 * are eight coins in general circulation:
 *
 *   1p, 2p, 5p, 10p, 20p, 50p, P1 (100p) and P2 (200p).
 *
 * It is possible to make P2 in the following way:
 *
 *   1P1 + 150p + 220p + 15p + 12p + 31p
 * 
 * How many different ways can P2 be made using any number of coins?
 *
 * ANSWER: 73682.
 */

#include <iostream>

static const int units[] = { 1, 2, 5, 10, 20, 50, 100, 200 };

static int number_of_ways(int sum, int max_unit)
{
	if (max_unit == 0)
		return 1;

	int partial_sum = 0;
	int ways = 0;
	for (int c = 0; partial_sum <= sum; partial_sum += units[max_unit])
	{
		ways += number_of_ways(sum - partial_sum, max_unit - 1);
	}
	return ways;
}

void solve_problem_31()
{
	int ways = number_of_ways(200, sizeof(units)/sizeof(units[0])-1);
	std::cout << ways << std::endl;
}
